/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2020年03月13日
*   版    本：v1.0.0
*   描    述：
*   Copyright (C) 2020 All rights reserved.
*   
* ================================================================*/


#include <iostream>
#include <vector>

using namespace std;

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode newhead = ListNode(-1);
        ListNode *p = &newhead;
        int size = lists.size();
        if(size == 0){
            return NULL;
        }

        int pos = -1;
        int min;
        while(true){
            min = INT_MAX;
            count = 0;
            pos = -1;
            for(int i = 0; i < size; i++){
                if(lists[i]){
                    if(min >= lists[i]->val){
                        pos = i;
                        min = lists[i]->val;
                    }
                }
            }
            if(pos >= 0){
                p->next = lists[pos];
                lists[pos] = lists[pos]->next;
                p = p->next;
            }else{
                break;
            }
        }

        return newhead.next;
    }
};
